COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	logic.3[s87,jmc]		1987 June version of logic for Daedalus
C00020 ENDMK
C⊗;
logic.3[s87,jmc]		1987 June version of logic for Daedalus

\section{Introduction} Before turning to logic in AI, we need some
facts about computer-based AI in general.

	The first person to see that efforts to make machines behave
intelligently could be based on programming computers was Alan Turing.
However, Turing (1950) didn't become widely known when it was first
published so that several other researchers reached the same conclusion
independently.  Before that people thought in terms of designing
machines, either machines directly oriented toward the problem
being solved or machines that purported to imitate some aspects
of the nervous system.

	Reliance on computers makes AI a branch of computer science.
As such it is concerned with the intellectual procedures that will
solve certain kinds of problems in certain kinds of information
situations.  When we look at AI problems at the procedure level,
we often conclude that certain kinds of procedures will solve
certain kinds of problems or even that certain kinds of procedures
are necessary for solving certain kinds of problems.  These conclusions
may be independent of whether the problem solver is a human, animal,
computer program or creature from Alpha Centauri.  To some extent
AI is analogous to other branches of computer science, e.g. linear
programming.  Indeed if most intellectual problems presented themselves
in the form of minimizing a linear function subject to linear inequalities
as constraints, then AI coincide with linear programming.  Actually,
there is only a tiny overlap with linear programming or any of the
other well known algorithmic branches of computer science.

	Thinking about the kind of problem the common sense world presents
and the devising ways of solving them is not the only possible approach
to understanding intelligence.  Another is based on experimental psychology.
It is interested in how humans solve problems, and its technique involves
giving people problems and seeing what they do.  Then one postulates
mechanisms to account for the behavior and tests them.  Today the testing
often involves programming these mechanisms on a computer and
comparing experimentally the behavior of the program with the behavior
of human subjects.  Indeed this use of computers revolutionized cognitive
psychology by overthrowing the behaviorist doctrine that was reluctant
to postulate internal mechanisms and was almost entirely interested in
looking for laws directly connecting stimulus and response.  Since humans
and animals have quite complex internal mechanisms, behaviorist psychology
didn't discover much about intelligence.  The actual research in cognitive
psychology overlaps artificial intelligence substantially, because AI
can get ideas about what mechanisms will succeed by observing humans,
and because results about what mechanisms will work are relevant to
human psychology.

	Another level of access to the mind is via neurophysiology.
One starts with the human or animal brain, determines its anatomy,
the physiology of neurons and their connection in higher level structures.
One attempts to trace the path of signals from the eye and ear and
determine how they control behavior.  This line of investigation has
the potential to determine how humans solve intellectual problems
independently of AI or cognitive psychology.  In addition to building
models based on the anatomy and physiology of the actual nervous system,
it is possible design systems for learning based on simplified models
of the neuron connected in ways that aren't direct simulations of
observed connections in the brain.  This is tempting, because it still
hasn't been possible to observe how the brain carries out higher level
mental functions.  This approach started in the 1950s, but many of
the researchers became discouraged in the 1960s and turned to other
approaches.  In the 1980s new ideas have revived the it under the
name of {\it connectionism}.  It has had some success in learning but
still hasn't attacked {\it sequential thinking} like that a human uses
to solve problems or to play games like chess.

	These three ways of studying intelligence are based on different
sources of information.  One is based on studying the world and the other
two are based on studying the brain.  None of them is likely to go away,
and each of them might lead to human-level artificial intelligence.
Their competition takes the form of a race rather than calling for
someone to decide which is the best bet.  Naturally there is co-operation
as well as competition, although not enough is known about the physiology
of the brain for there to be much contact between AI and real neurophysiology.
There is a considerable potential for mutual influence between AI and
connectionism, but not much has been realized.

	We now say goodbye to cognitive psychology, neurophysiology and
connectionism
for the balance of this paper and concentrate on AI as a branch of computer
science.

	Computers can carry out explicit sequential processes much faster
than people.  Therefore, solving problems by search of spaces of alternatives
began already in the 1950s, and the two most interesting subjects were
chess and mathematical theorem proving.

	The most obvious way for a computer to play chess is to examine
legal moves and their successors to some fixed depth, evaluate the
resulting positions according to approximate rules that can be found
in chess books, and decide which move to make according to the
evaluation of the lines of play considered for the machine and its
opponent.  Shannon (1950) discussed such a program, and programs
were implemented in the 1950s.  It's not clear whether any researcher
way naive enough to expect a straightforward program along these lines
to play expert level chess.  The first programs played very badly.
Nevertheless, present programs, which play at master level, are based
on elaborations of this basic idea.  The improvements are partly based
on faster computers but mainly on implementing some {\it intellectual
mechanisms} that the AI researchers observe in their own play.  We
mention two solved problems and two unsolved problems.

	1. The horizon effect.  If the program looks to a fixed depth and
evaluates the resulting position according to rules taken from chess
books, it will err badly by postponing recognizing disasters beyond its
``horizon''.  For example, it will like positions in which it has just
made a capture not noticing that a recapture refuting the move is about to
occur.  Therefore, it is necessary to apply the ``static evaluation'' only
to ``quiescent positions'' and to continue the search from active
positions.  This is done reasonably well by present programs.

	2. The alpha-beta heuristic.  A full description would be
too long, so we give only an example.  Suppose the machine considers
a possible move and notices an opponent's reply that refutes the move,
i.e. causes the machine a big loss.  Early chess programs will nevertheless
consider other moves of the opponent, thus wasting its computer time.
The so-called alpha-beta heuristic quits evaluating a position when
it finds a move that refutes the move leading to the position.  Using
alpha-beta sometimes reduces the number of positions that have to be evaluated
to the square root of what it would be otherwise, e.g. from $10↑12$ to
$10↑6$.  While alpha-beta was not discovered in full generality till
about 1960, it seems to be a ``compulsory heuristic'' --- needed
whether the chess player is a man or a machine, and it's easy to
see that we humans use it. The delay in its
discovery represents a failure in human self-observation even though
it seems obvious once mentioned.  Very likely there are many current
failures in self-observation that will also seem obvious once discovered
and pointed out.

	3. Decomposition of positions.  It is often necessary to
recognize a situation as composed of subsituations which can be
analyzed separately.  After the identification of the subsituations
and their separate analysis, there interaction is analyzed.  In
many cases this gets answers that could be obtained from analysis
of the situation as a whole that is to complex to be computationally
practical.  Present chess programs only analyze the position as
a whole and rely on the computational power of the computer to
compete with humans who recognize and analyze subpositions.  It
is clear that to play the Japanese game of {\it go} well enough to
compete with good human players, computers will have to recognize
subsituations.  Since it is not yet understood how to do this,
present {\it go} programs are very bad.

	4. Labelling bad moves.  Consider a really bad
move that both humans and computer programs readily recognize as bad.
Suppose that the move is available not only in the present position
but in tens of thousands of future positions that are looked at
in the computer analysis.  Present computer programs will repeat
the analysis that led to rejecting the move tens of thousands of
times.  Human players reject it once and revive it only if
future positions looked at has some new feature that triggers its
revival.  This is necessary for efficiency but introduces the
possibility of error, because one might not notice a feature
justifying looking at the move.  We don't understand how humans
do it well enough to program computers to reject bad moves only
once without making an unacceptable number of errors.

	The point of these chess examples is that progress in AI
depends on the identification and programming of intellectual
mechanisms.  There doesn't seem to be any special barrier to
finding these mechanisms; we just need more smart people to think
about them.

	Programming computers to prove mathematical theorems is
an even more complex area.  General techniques, independent
of the subject matter, were developed again
starting in the 1950s.  These techniques have so far given results
comparable to human theorem proving only in a few domains where
human intuition is lacking, but this is still an active field and
progress continues.  Interactive theorem proving, where the human
proposes intermediate results and the computer does the detailed
computation has been more successful.  The most striking results
so far, in my opinion, are the proofs by Shankar (1986, 1987) of
the Church-Rosser theorem (for which many wrong proofs have been
given) and the G/:odel incompleteness theorem.  Further progress
in automatic theorem proving depends on inventing a good way of
providing the computer with domain dependent heuristics.

	For lack of space and time we won't discuss AI work in the sensory
and motor areas, e.g. speech and picture recognition, the control of
robots and computational linguistics.  We only remark that thes studies
use both the AI associated techniques of search and pattern recognition
and more conventional mathematical methods such as Fourier
analysis and geometry.

	Pattern matching has been a key technique in most AI work, and
the kinds of patterns that can be matched in data have steadily become
more sophisticated.